package top.ddltech.algorithm.search;

/**
 * 基于线性探测法的散列表
 */
public class LinearProbingHash<Key, Value> {

    // 散列表中键值对的总数
    private int N;
    // 线性探测表的大小
    private int M = 16;
    // 键
    private Key[] keys;
    // 值
    private Value[] vals;

    public LinearProbingHash(int capacity) {
        M = capacity;
        N = 0;
        keys = (Key[]) new Object[M];
        vals = (Value[]) new Object[M];
    }

    private int hash(Key key) {
        return (key.hashCode() & 0x7fffffff) % M;
    }

    private void resize(int capacity) {
        LinearProbingHash<Key, Value> temp = new LinearProbingHash<Key, Value>(capacity);
        for (int i = 0; i < M; i++) {
            if (keys[i] != null) {
                temp.put(keys[i], vals[i]);
            }
        }
        keys = temp.keys;
        vals = temp.vals;
        M = temp.M;
    }

    public void put(Key key, Value val) {
        if (N >= M / 2) {
            // 将M加倍
            resize(2 * M);
        }
        int i;
        for (i = hash(key); keys[i] != null; i = (i + 1) % M) {
            if (keys[i].equals(key)) {
                vals[i] = val;
                return;
            }
        }
        keys[i] = key;
        vals[i] = val;
        N++;
    }

    public Value get(Key key) {
        for (int i = hash(key); keys[i] != null; i = (i + 1) % M) {
            if (keys[i].equals(key)) {
                return vals[i];
            }
        }
        return null;
    }
}
